|
|
|
\require{AMSmath}
Reageren...
Re: Re: Parabool met gegeven helling
Hallo,
Ik heb een (eenvoudige) opgave gekregen ivm RSA.
De gegevens zijn:
n = 10201
v = vercijfelsleutel = 71
Gevraagd: bepaald o = ontcijfersleutel
Ik probeer dit op te lossen, maar ik weet even niet hoe ik verder moet:
Wat ik al heb is dit:
p & q zijn priemgetallen
n = p*q, dus na enig zoekwerk weet je dat p en q = 101
(p-1)*(q-1) = 100*100 = 10000
Ik weet dat:
o * v congruent is met 1(mod 10000)
dus:
o * 71 is congruent met 1 (mod 10000)
Vervolgens bepaal ik de kettingbreuk hiervan:
10000/71
= 140 + 1/(1+1/(5+1/(2+1/5)))
Mijn probleem is dat ik nu niet meer weet hoe ik verder moet.
Iemand enig idee?
(met maple kom ik 1831 uit (msolve-commando), maar ik had graag geweten hoe ik het handmatig doe)
Dank bij voorbaat,
Vincent Claeys
Antwoord
De vraag komt neer op 'hoe bereken je de inverse van 71 (mod 10000)?'
Eerst de ggd van 71 en 10000 berekenen:
10000 = 140 · 71 + 60 Þ 60 = 10000 - 140 · 71
71 = 1 · 60 + 11 Þ 11 = 71 - 1 · 60
60 = 5 · 11 + 5 Þ 5 = 60 - 5 · 11
11 = 2 · 5 + 1 Þ 1 = 11 - 2 · 5
Nu terug rekenen:
1 = 11 - 2 · 5
1 = 1 · 11 - 2 · (60 - 5 · 11)
1 = 11 · 11 - 2 · 60
1 = -2 · 60 + 11 · (71 - 1 · 60)
1 = -13 · 60 + 11 · 71
1 = 11 · 71 - 13 · (10000 - 140 · 71)
1 = 1831 · 71 - 13 · 10000
de inverse van 71 (mod 10000) is 1831 (mod 10000)
Controle:
71 · 1831 = 130001
130001 (mod 10000) = 1
Gebruik dit formulier alleen om te reageren op de inhoud van de vraag en/of het
antwoord hierboven. Voor het stellen van nieuwe vragen kan je gebruik maken
van een vraag stellen in het menu aan de linker kant. Alvast bedankt!
|
